1. Field of the Invention
This invention relates to a method and apparatus for automatically setting a background level in an imaging system, and more particularly to a method and apparatus for determining threshold levels in an image scanning system.
2. Description of Related Art
A typical image scanner partitions an image of, for example, a sheet of paper into multiple areas called pixels. When the sheet of paper is illuminated, each pixel will have a reflectivity value falling within a continuous range from the darkest pixel reflectivity value to the lightest pixel reflectivity value. The image scanner then quantizes each value from the range of continuous values into one of a set of discrete values. The quantization process requires a set of threshold values to determine which continuous values correspond to a certain discrete value. The optimum set of thresholds is a function of the nature of the image being scanned including, for example, the background color of the paper.
Since it is desirable that a particular image scanner be capable of scanning images from a variety of types of sources, the threshold levels are designed to vary. Many image scanners have manual controls allowing the operator to vary the threshold levels; but this arrangement by itself is an unsatisfactory solution to the problem of setting threshold levels because manual intervention makes the machine more difficult to use. Thus, a number of methods have been proposed to automatically determine a background level from which a set of thresholds may be determined. One method involves averaging reflectivity values in a selected area near the beginning of a document to be scanned. The problem with this method is that the selected area may not be representative of the document and may instead be a border decoration area, for example.
Another method involves setting the background level based on the average pixel reflectivity value in a scan line. The average pixel reflectivity value is an appropriate basis for background level, however, only when the image being scanned is one having a small number of lines, such as an engineering drawing. The documents in a typical office environment are not necessarily limited to those having a small number of lines.
Another method involves prescanning the document to detect the highest and lowest pixel reflectivity values and then selecting threshold levels to obtain maximum resolution. One problem with this method is that the highest reflectivity value detected in a scan line may be the result of noise and therefore an inappropriate basis for setting the background level. Another problem is the requirement of a prescan, which limits document throughput. Further, a prescan may be impractical for some scanning applications such as, for example, applications employing a constant velocity transport system.
One method put into commercial use involves the construction of a histogram during a prescan of the image to be scanned. A histogram may be visualized as a graph, such as the one shown in FIG. 1, having reflectivity on the horizontal axis and the number of pixels having a certain reflectivity on the vertical axis. The 7650 ProImager scanner, manufactured by Xerox Corporation, constructs a histogram by prescanning the image to be scanned. The histogram is then analyzed to determine the highest pixel reflectivity value by starting with the right most nonzero point on the horizontal axis of the histogram and counting the number of pixels. Pixels in the histogram are continually counted while moving left on the horizontal axis until the number of pixels counted is equal to 5% of the total number of pixels in a scan line. The reflectivity value where this occurs is taken to be the background level. The lowest reflectivity value is determined in an analogous fashion by starting at the left most nonzero point on the horizontal axis and moving right. These highest and lowest reflectivity values are used to construct a mapping function that maps a video signal onto the interval from 0 to 255, and the mapped video signal is then thresholded or screened normally. This method produces high and low background values that tend to be independent of noise, but the method has the disadvantage of requiring a prescan of the document to be scanned.
A method not requiring a prescan is disclosed in U.S. Pat. No. 4,850,029 to Moyer filed July 15, 1985. This method involves the running calculation of a number of different types of averages that are constantly updated to produce a value indicative of the average pixel value of a document. Moyer, however, is directed to determining an average white value and using this average white value only to calculate a threshold value. Although an average white value might be used to estimate a threshold value, it may not be suitable for more general applications, such as mapping of pixel reflectivity values. Further, Moyer involves a relatively complicated algorithm that is preferably implemented with a microprocessor. Although the speed limitation incurred by using a microprocessor might be acceptable for some applications, for others it would not be acceptable. For example, in many scanners the data rate exceeds 10 million pixels per second, which would be a difficult for a microprocessor to achieve while running the Moyer algorithm. Moyer discloses a technique of skipping pixels to increase document throughput, but skipping pixels can lead to drastic inaccuracies in threshold calculation, particularly on documents with periodic structures. Additional speed might be gained by implementing the algorithm of Moyer on a special purpose chip, but that would involve additional hardware expense.